/**
 * @version: V1.0
 * @Title: Test03_GetSuccessorNode.java
 * @Description:
 * @author wangshipeng
 * @date 2022-01-24 22:47
 * @Copyright: 2022-01-24
 */

package com.peng.tree.test_code;


/**
 * @author wangshipeng
 * @ClassName: Test03_GetSuccessorNode
 * @Description: 给定一个节点，获取此节点的后继节点
 * <p>
 * 后继节点:  X的后继节点就是中序遍历中，X节点的后面一个节点
 * @date 2022-01-24 22:47
 */
public class Test03_GetSuccessorNode {

    public static Node getSuccessor(Node node) {

        if (node == null) {
            return null;
        }
        //如果有右孩子，则来到右孩子的最左节点，就是后继节点
        if (node.right != null) {
            node = node.right;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }
        //如果没有右孩子，则一路向上找父亲，直到该节点是它父节点的左孩子，则父节点就是该节点的后继节点
        Node parent = node.parent;
        while (parent != null && parent.right == node) {
            node = parent;
            parent = node.parent;
        }

        return parent;


    }

    public static void main(String[] args) {
        Node node = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);

        node.left = node2;
        node2.parent = node;
        node.right = node3;
        node3.parent = node;

        node2.left = node4;
        node2.right = node5;
        node4.parent = node2;
        node5.parent = node2;


        node3.left = node6;
        node3.right = node7;
        node6.parent = node3;
        node7.parent = node3;

        node4.left = node8;
        node4.right = node9;
        node8.parent = node4;
        node9.parent = node4;
        /*
                   1
             2              3
           4    5         6     7
         8   9

         */
        Node successor = getSuccessor(node9);
        System.out.println(successor.val);
    }

    public static class Node {
        private Node left;
        private Node right;
        private Node parent;
        private Integer val;

        public Node(Integer val) {
            this.val = val;
        }
    }


}
